#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> fi;
    vector<int> countBits(int n) {
        fi.resize(31);
        for (int i = 0; i < 31; ++i) fi[i] = pow(2, i);

        vector<int> ret(n + 1);
        for (int i = 0; i <= n; ++i)
        {
            ret[i] = bitC(i);
        }

        return ret;
    }

    int bitC(int x)
    {
        int count = 0;
        while (x)
        {
            auto pos = upper_bound(fi.begin(), fi.end(), x) - fi.begin() - 1;
            count++;
            x -= fi[pos];
        }

        return count;
    }
};